package com.future;

import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Description:
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/closest-subsequence-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author weiruibai.vendor
 * Date: 2022/3/22 09:52
 */
public class Solution_minAbsDifference_1755_v2 {

    public static void main(String[] args) {

        int maxLength = 40;
        int maxVal = 10_000_000;
        int testTimes = 1_000;
        int maxGoal = 1_00;
        System.out.println("test start");
        for (int i = 0; i < 0; i++) {
            System.out.println("运行第" + i + "个");
            int[] nums = generateRandomArr(maxLength, maxVal);
            int goal = (int) ((1 + maxGoal) * Math.random());
            // int a1 = minAbsDifference(nums, goal);
            int a1 = minAbsDifference_2(nums, goal);
            int a2 = minAbsDifference_good(nums, goal);
            if (a2 != a1) {
                System.out.println("nums=" + Arrays.toString(nums));
                System.out.println("goal=" + goal);
                System.out.println("real ans=" + a1);
                System.out.println("my ans=" + a2);
                throw new RuntimeException();
            }
        }
        System.out.println("test finished");
        int[] nums = {7,-9,15,-2};
        int goal = -5;
        //System.out.println(minAbsDifference(nums, goal));
        System.out.println(minAbsDifference_good(nums, goal));
        System.out.println(minAbsDifference_2(nums, goal));

    }


    public static int[] l = new int[1 << 20];
    public static int[] r = new int[1 << 20];

    public static int minAbsDifference_good(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return goal;
        }
        // 比如le=16,说明数组l只有16个数字，其他都是0，这样可以做到只对前le个数进行增量排序
        int le = process(nums, 0, nums.length >> 1, 0, 0, l);
        int re = process(nums, nums.length >> 1, nums.length, 0, 0, r);
        Arrays.sort(l, 0, le);
        Arrays.sort(r, 0, re--);
        int ans = Math.abs(goal);
        for (int i = 0; i < le; i++) {
            int rest = goal - l[i];
            while (re > 0 && Math.abs(rest - r[re - 1]) <= Math.abs(rest - r[re])) {
                re--;
            }
            ans = Math.min(ans, Math.abs(rest - r[re]));
        }
        return ans;
    }

    /**
     * 返回的是数组的最后有效下标
     *
     * @param nums
     * @param index
     * @param end
     * @param sum
     * @param fill
     * @param arr
     * @return
     */
    public static int process(int[] nums, int index, int end, int sum, int fill, int[] arr) {
        if (index == end) {
            arr[fill++] = sum;
        } else {
            fill = process(nums, index + 1, end, sum, fill, arr);
            fill = process(nums, index + 1, end, sum + nums[index], fill, arr);
        }
        return fill;
    }

    private static int[] generateRandomArr(int maxLength, int maxVal) {
        int reaLength = (int) ((maxLength + 1) * Math.random());
        int[] arr = new int[reaLength];
        for (int i = 0; i < reaLength; i++) {
            arr[i] = (int) ((maxVal + 1) * Math.random());
        }
        return arr;
    }

    /**
     * 分治
     *
     * @param nums
     * @param goal
     * @return
     */
    public static int minAbsDifference_2(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return goal;
        }
        int ans = Math.abs(goal);
        int[] leftHalfArr = new int[1 << 20];
        int[] rightHalfArr = new int[1 << 20];

        AtomicInteger lAtomIndex = new AtomicInteger(0);
        AtomicInteger rAtomIndex = new AtomicInteger(0);
        process_2(nums, 0, nums.length >> 1, lAtomIndex, 0, leftHalfArr);
        int realLIndex = lAtomIndex.get();
        process_2(nums, nums.length >> 1, nums.length, rAtomIndex, 0, rightHalfArr);
        int realRIndex = rAtomIndex.get();
        Arrays.sort(leftHalfArr, 0, realLIndex);
        // 注意这里的realRIndex--，不能为--realRIndex
        Arrays.sort(rightHalfArr, 0, realRIndex--);
        for (int i = 0; i < realLIndex; i++) {
            int rest = goal - leftHalfArr[i];
            while (realRIndex > 0 && Math.abs(rest - rightHalfArr[realRIndex - 1]) <= Math.abs(rest - rightHalfArr[realRIndex])) {
                realRIndex--;
            }
            ans = Math.min(ans, Math.abs(rest - rightHalfArr[realRIndex]));

        }
        return ans;
    }

    private static void process_2(int[] nums, int curIndex, int end, AtomicInteger reaIndex, int sum, int[] leftHalfArr) {
        if (curIndex == end) {
            leftHalfArr[reaIndex.getAndIncrement()] = sum;
        } else {
            process_2(nums, curIndex + 1, end, reaIndex, sum, leftHalfArr);
            process_2(nums, curIndex + 1, end, reaIndex, sum + nums[curIndex], leftHalfArr);
        }
    }

    /**
     * 暴力方法
     *
     * @param nums
     * @param goal
     * @return
     */
    public static int minAbsDifference(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return goal;
        }
        int ans = process(nums, 0, goal);

        return ans;
    }

    private static int process(int[] nums, int index, int rest) {
        if (index == nums.length) {
            return Math.abs(rest);
        }
        int v1 = process(nums, index + 1, rest);
        int v2 = process(nums, index + 1, rest - nums[index]);
        return Math.min(v1, v2);
    }

}
